//给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。 
//
// 示例 1: 
//
// 输入: 
//[
//  [1,1,1],
//  [1,0,1],
//  [1,1,1]
//]
//输出: 
//[
//  [1,0,1],
//  [0,0,0],
//  [1,0,1]
//]
// 
//
// 示例 2: 
//
// 输入: 
//[
//  [0,1,2,0],
//  [3,4,5,2],
//  [1,3,1,5]
//]
//输出: 
//[
//  [0,0,0,0],
//  [0,4,5,0],
//  [0,3,1,0]
//] 
//
// 进阶: 
//
// 
// 一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。 
// 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。 
// 你能想出一个常数空间的解决方案吗？ 
// 
// Related Topics 数组 
// 👍 342 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：矩阵置零
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P73_SetMatrixZeroes {
    public static void main(String[] args) {
        Solution solution = new P73_SetMatrixZeroes().new Solution();
        int[][] matrix = {
                {1, 0, 3}
        };
        MyUtil.print("处理前");
        MyUtil.printInt(matrix);
        solution.setZeroes(matrix);
        MyUtil.print("处理后");
        MyUtil.printInt(matrix);
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 记录0元素的第一行的第一个数和第一列的第一个数为0。要注意首先记录首行和首列是否有0
     * <p>
     * 时间复杂度 O(m*n)
     * 空间复杂度 O(1)
     */
    class Solution {
        public void setZeroes(int[][] matrix) {
            if (matrix == null || matrix.length == 0) {
                return;
            }
            // 记录首行是否有0
            boolean firstRow = false;
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[0][j] == 0) {
                    firstRow = true;
                    break;
                }
            }
            // 记录首列是否有0
            boolean firstCol = false;
            for (int i = 0; i < matrix.length; i++) {
                if (matrix[i][0] == 0) {
                    firstCol = true;
                    break;
                }

            }
            // 记录0元素的第一行的第一个数和第一列的第一个数为0
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == 0) {
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                    }
                }
            }
            // 处理非首行首列，将行首为0的整行置为0，列首为0的整列置为0
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 1; j < matrix[0].length; j++) {
                    if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                        matrix[i][j] = 0;
                    }
                }
            }
            // 处理首行
            if (firstCol) {
                for (int i = 0; i < matrix.length; i++) {
                    matrix[i][0] = 0;
                }
            }
            // 处理首列
            if (firstRow) {
                for (int j = 0; j < matrix[0].length; j++) {
                    matrix[0][j] = 0;
                }
            }
        }
    }

//    /**
//     * 记录0元素的x和y坐标集
//     * 时间复杂度 O(m*n)
//     * 空间复杂度 O(m+n)
//     */
//    class Solution {
//        public void setZeroes(int[][] matrix) {
//            if (matrix == null || matrix.length == 0) {
//                return;
//            }
//            // 0的x坐标集
//            Set<Integer> xSet = new HashSet<>();
//            // 0的y坐标集
//            Set<Integer> ySet = new HashSet<>();
//            // 循环一遍找出0的x和y的坐标集
//            for (int i = 0; i < matrix.length; i++) {
//                for (int j = 0; j < matrix[0].length; j++) {
//                    if (matrix[i][j] == 0) {
//                        xSet.add(i);
//                        ySet.add(j);
//                    }
//                }
//            }
//            // 再循环将行和列的所有元素都设为0
//            for (int i = 0; i < matrix.length; i++) {
//                for (int j = 0; j < matrix[0].length; j++) {
//                    if (xSet.contains(i) || ySet.contains(j)) {
//                        matrix[i][j] = 0;
//                    }
//                }
//            }
//        }
//    }
    //leetcode submit region end(Prohibit modification and deletion)

}